package com.leetcode;

import com.leetcode.common.TreeNode;

/**
 * 110. 平衡二叉树
 * 自底向上的递归
 *
 * @author fy
 * @date 2022/4/20 21:14
 */
public class Solution110_1 {

    public boolean isBalanced(TreeNode root) {
        return height(root) >= 0;
    }

    /**
     * 返回root节点树的高度, 如果不是平衡的, 返回-1
     * 自顶向下递归，因此对于同一个节点，函数 height 会被重复调用，
     * 导致时间复杂度较高。如果使用自底向上的做法，则对于每个节点，
     * 函数 height 只会被调用一次
     *
     * @param root
     * @return
     */
    public int height(TreeNode root) {
        // 返回root树的高度
        if (root == null) {
            return 0;
        }
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        // 如果有任意的左右子树不是平衡的,则直接返回
        if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        } else {
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }

}
